#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Software: PyCharm
# @Version : Python-
# @Author  : Shengji He
# @Email   : hsjbit@163.com
# @File    : CountPrimes.py
# @Time    : 2020/12/3 10:07
# @Description:
from math import sqrt


class Solution:
    def countPrimes(self, n: int) -> int:
        """
        Count the number of prime numbers less than a non-negative number, n.

        Example 1:
            Input: n = 10
            Output: 4
            Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.
        Example 2:
            Input: n = 0
            Output: 0
        Example 3:
            Input: n = 1
            Output: 0

        Constraints:
            - 0 <= n <= 5 * 106

        :param n: 
        :return: 
        """
    #     cnt_prim = [True] * n
    #     for i in range(2, int(sqrt(n)) + 1):
    #         if self.isPrimes(i):
    #             for j in range(i * i, n, i):
    #                 cnt_prim[j] = False
    #
    #     return sum(cnt_prim[2:])
    #
    # def isPrimes(self, num):
    #     if num <= 3:
    #         return num > 1
    #     if num % 6 != 1 and num % 6 != 5:
    #         return False
    #     for i in range(5, int(sqrt(num)) + 1, 6):
    #         if num % i == 0 or num % (i + 2) == 0:
    #             return False
    #     return True
        cnt_prim = [True] * n
        for i in range(2, int(sqrt(n)) + 1):
            if cnt_prim[i]:
                cnt_prim[i * i: n : i] = [False] * ((n - 1 - i * i) // i + 1)
                # for j in range(i * i, n, i):
                #     cnt_prim[j] = False

        return sum(cnt_prim[2:])

        
if __name__ == '__main__':
    S = Solution()
    n = 10
    print(S.countPrimes(n))
    print('done')
